In recent years a widespread use of digital techniques for storing and transmitting information has been witnessed. The success of these techniques is due to the availability of cost effective hardware components. Among network technologies dedicated to the above cited services, the ATM technique (Asynchronous Transfer Mode) permits the transmission of multi-media information in a flexible and efficient manner. The ATM technique was developed to solve all aspects of multi-media applications, video, audio, and data transmissions on a same network, with the same protocol, regardless of the type of network (LAN, MAN or WAN).
The ATM technology provides for a bandwidth with a variable bit-rate that may reach the order of Gigabit/sec and a scalability of the number of network nodes as required by the general architecture of switched networks. Differently from switched circuit networks, the ATM packet-switched network has the advantage of engaging the channel only during the actual transfer of information.
The procedure of traffic control of ATM networks has not yet reached a consolidated standard, with many problems still remaining to be solved. One of the main problems of this technology is the possible loss of packets, which in case of video transmissions may result in a degradation of the images that exceeds acceptable levels. Indeed, in some instances the average loss of packets may reach peaks of about 5%. A loss of packets may occur for different causes:
when the packets arrive after the maximum permitted time delay; PA1 when the buffer overflows, that is, when its filling threshold is exceeded; or PA1 when traffic congestion occurs due to an abrupt variation of the information flow or network hardware problems. PA1 the PU (processing unit) module, which carries out the decoding itself by solving the relative systems of equations; PA1 the CU (Control Unit) module, which interfaces the PU module with the external world, adapts and synchronizes the PET decoder with other external devices, taking into account of the different clocks, recognizes whether or not the format is of the PET type, and supplies to the PU module the information contained in the incoming data packets, in a correct order and format.
If traffic congestion occurs and some packets are lost, the network is unable to ensure satisfactory service. To provide for adequate bandwidth characteristics, an ATM-base should have the ability to implement a traffic control procedure like, for example, a Call Admission Control (CAC) or of a local control at node level (control of the average and peak number of packets reading the interconnection buffers). Although such procedures may be implemented at their best, packet losses would be in any case inevitable because of the intervention of policing structures through intelligent agents, and in the case of machine malfunctions.
The method developed by Berkeley and referred to as PET (Priority Encoded Transmission)are disclosed in A. Albanese, J. Blomer, J. Edmonds, M. Luby: Priority Encoding Transmission, Technical report, International Computer Science Institute, Berkeley, Calif., August 1994. The method is based on coding the information with different levels of redundancy depending on its importance.
The PET technique is based upon a redundant coding of original information distributed over a plurality of distinct packets. The redundance added during the coding phase is such that, even in case of loss of coded packets, the original information can be fully retrieved from the information existing in the remaining packets.
The PET Coding Algorithm
The PET coding technique as disclosed in M. O. Rabin: Efficient Dispersal of Information for Security, Load Balancing and Fault Tolerance, Journal of the Association for Computing Machinery, Vol. 36, No. 2, April 1989, is an algorithm of information dispersion that includes adding, to the message to be transmitted, a proper redundance, before dividing this encoded message into a plurality of portions which represent the packets that are sent through the transmission medium. Even by receiving only a fraction of the total number of the packets it is possible to reconstruct the original message. See also R. Storn: Modeling and Optimization of PET-Redundancy Assignment for MPEG Sequences, Technical report, International Computer Science Institute, Berkeley, Calif., August, May 1995.
The original information stream is divided into a set of messages, coded independently one from the other, as depicted in FIG. 1. Hence, each message is divided into segments, each having a certain priority grade. The priority is generally specified in terms of the minimum percentage of packets of the whole message required to correctly decode the segment as disclosed, for example, in A. Albanese, M. Kalfane, B. Lamparter, M. Luby: Application Programmer Interface to PET, Technical report, International Computer Science Institute, Berkeley, Calif., Aug. 25, 1995; and C. Leichner: Hierarchical Encoding of MPEG Sequences using Priority Encoding Transmission (PET), Dissertation, International Computer Science Institute, Berkeley, Calif., November 1994.
The number of blocks for each segment depends on its length and corresponding priority. The priority of a segment is expressed in terms of its blocks' length: the higher the priority the shorter are the blocks, as shown in FIG. 2. For each segment, the length of the block is the same, because they have the same priority.
The PET coding technique includes considering the m words of the different blocks as the coefficients of a polynomial of order m-1 over a Galois field GF[p], as illustrated in FIG. 3. The polynomial of order m-1, evaluated at different n points over a Galois field GF[p], is uniformly distributed on n packets.
The current implementation of the PET technique is based on erasure codes and considers the use of integer arithmetic instrumental within the Galois field GF[p] (that is the field of the rest of p modulus), within which all the operations are with modulus p. The original information stream is considered as a sequence of unitary elements (for example, bytes of 8 bits or words of 16 bit), which for simplicity in the ensuing text will be referred to as "words".
After having divided the messages into segments, the segments are partitioned into blocks, so that all blocks of the same segment have the same length m (represented by the number of words) according to a scheme as that depicted in FIG. 4. Of course, blocks belonging to different segments may have different lengths.
The m words of each block are considered as the coefficients of a polynomial of order m-1 over the GF[p] field:
p(x)=a.sub.0 +a.sub.1 x+a.sub.2 x.sup.2 + . . . +a.sub.m-1 x.sup.m-1
The coding of the block is formed by the sequence of the n words (n.gtoreq.m) obtained by evaluating the polynomial at n distinct points of GF[p]. These n values are distributed in n packets so that each packet contains only one value of p(x), calculated in a distinct point of GF[p].
The above described algorithm is repeated for each single block of each segment, and the sequence of packets that encode the original message is obtained by grouping within the same packet the polynomial values evaluated for the same point of GF[p] relative to all the segments. In this way, the information relative to each segment is uniformly spread over all the packets.
Of course, when words of 16 bits are mapped over the field GF[2.sup.16 +1], there will be a high probability of not using an element of the Galois field. To avoid possible overflow problems, it is possible to operate always with units of 16 bits (even after the mapping), by eliminating the unused element and keeping its location (which will be referred to as its offset or by the symbol .epsilon.) properly stored to be able to recover the original value after having completed the execution of the required operations.
Besides the offset of the point at which the polynomial is evaluated, it is necessary to introduce the information relative to the priority of the various segments and to their length, to be able to exactly reconstruct the original message. This information defines a further segment, which in the ensuing description will be referred to as the Priority Table or briefly PT. The priority of the PT segment must be at least equal to that of the segment of highest priority of the message, to make possible the decoding of such a PT segment without waiting for a correct reception of other packets.
Decoding of a segment
First, a decoder must ascertain that the number of packets received is equal to at least the minimum number m required. By assuming that this basic requirement is fulfilled, a vector D of the GF[p] points over the Galois field to which the relative packets, determining this from the packet's headers themselves, is initialized. ##EQU1##
Starting from said D vector an m*m square matrix A may create ##EQU2##
It should be noticed that the j-th column of matrix A is provided by the j-th powers of the elements of the vector D. Thus, the decoder must consider all the corresponding words of the m packets relative to the same block (into which the segments are subdivided). These words represent, in a coded form, the m polynomial values associated with the block itself. The decoder must then decode taking into account the respective offset (d), stored in the header, and reconstruct the vector B with the resulting polynomial values: ##EQU3##
At this stage the decoder must solve the linear system EQU Ax=B (2)
where x is a column-vector of m elements, thus obtaining the m words of the original block.